/**
 * 
 * 思路，默认第一个已经被排序了，然后往后遍历，将后续元素逐个插入到已排序好的数组中
 */
function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let j = i - 1
    // 保存当前要插入的值，因为其当前位置要被用于辅助覆盖
    let curVal = arr[i]
    while (j >= 0 && curVal < arr[j]) {
      // 如果要从小到大排序，有序数组的尾端不是大于当前值，则代表还没有找到插入位置，接着找下一个空位
      arr[j + 1] = arr[j]
      j--
    }
    // 找到比自己小的位置，在后方插入
    arr[j + 1] = curVal
  }
  console.log(arr);
  return arr
}
insertSort([4, 2, 5, 3, 6, 1, 3, 8])